package com.LeeCode;

/**
 * 水果成篮 III
 */

public class Code3479 {
    public static void main(String[] args) {

    }

    class SegmentTree {
        private final int[] max;

        public SegmentTree(int[] a) {
            int n = a.length;
            max = new int[2 << (32 - Integer.numberOfLeadingZeros(n - 1))];
            build(a, 1, 0, n - 1);
        }

        // 找区间内的第一个 >= x 的数，并更新为 -1，返回这个数的下标（没有则返回 -1）
        public int findFirstAndUpdate(int o, int l, int r, int x) {
            if (max[o] < x) { // 区间没有 >= x 的数
                return -1;
            }
            if (l == r) {
                max[o] = -1; // 更新为 -1，表示不能放水果
                return l;
            }
            int m = (l + r) / 2;
            int i = findFirstAndUpdate(o * 2, l, m, x); // 先递归左子树
            if (i < 0) { // 左子树没找到
                i = findFirstAndUpdate(o * 2 + 1, m + 1, r, x); // 再递归右子树
            }
            maintain(o);
            return i;
        }

        private void maintain(int o) {
            max[o] = Math.max(max[o * 2], max[o * 2 + 1]);
        }

        // 初始化线段树
        private void build(int[] a, int o, int l, int r) {
            if (l == r) {
                max[o] = a[l];
                return;
            }
            int m = (l + r) / 2;
            build(a, o * 2, l, m);
            build(a, o * 2 + 1, m + 1, r);
            maintain(o);
        }
    }

    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        SegmentTree t = new SegmentTree(baskets);
        int n = baskets.length;
        int ans = 0;
        for (int x : fruits) {
            if (t.findFirstAndUpdate(1, 0, n - 1, x) < 0) {
                ans++;
            }
        }
        return ans;
    }
}
